package com.ycz.algorithm.utils.sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author yancz
 * @ClassName SortUtils
 * @description: // 排序工具类
 * @date 2025-03-01 18:23:10
 * @version: 1.0
 */
public class SortUtils {

    /*
     * @author yancz
     * @description // 1.直接选择排序算法，时间复杂度O(n^2)，空间复杂度O(1)，不稳定排序
     * @date 2025/3/1 18:34
     * @param nums
     * @return void
     */
    public static void selectionSort(int[] nums) {
        int size = nums.length;
        for (int i = 0; i < size - 1; i++) { // 遍历未排序部分，最后一个元素已排序，所以区间是[0, size-2]
            int k = i; // 记录最小元素的索引
            for (int j = i + 1; j < size; j++) {
                if (nums[j] < nums[k]) {
                    k = j; // 找到最小元素的索引
                }
            }
            swapElements(nums, i, k); // 操作数组，交换最小元素和当前元素的位置
        }
    }


    /*
     * @author yancz
     * @description // 2.冒泡排序，时间复杂度O(n^2)，空间复杂度O(1)，稳定排序
     * @date 2025/3/1 18:57
     * @param nums
     * @return void
     */
    public static void bubbleSort(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) { // 外层循环，未排序部分的长度，区间是[0, i]
            for (int j = 0; j < i; j++) { // 内层循环，将未排序区间[0, i]中的最大元素放到末尾
                if (nums[j] > nums[j + 1]) {
                    swapElements(nums, j, j + 1);
                }
            }
        }
    }

    /*
     * @author yancz
     * @description // 冒泡排序优化，时间复杂度O(n^2)，空间复杂度O(1)，稳定排序，如果输入数组已经有序，则不用再排序，可将时间复杂度降低到O(n)
     * @date 2025/3/1 19:00
     * @param nums
     * @return void
     */
    public static void bubbleSortSwitchFlag(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            boolean flag = false; // 标志位
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swapElements(nums, j, j + 1);
                    flag = true; // 发生交换，标志位置为true
                }
            }
            if (!flag) break; // 如果没有发生交换，则说明数组已经有序，则退出最外层循环
        }
    }

    /*
     * @author yancz
     * @description // 3.插入排序，时间复杂度O(n^2)，空间复杂度O(1)，稳定排序，当输入数组已经有序时，时间复杂度O(n)
     * @date 2025/3/1 19:07
     * @param nums
     * @return void
     */
    public static void insertionSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) { // 外层循环，第一个元素已排序，无需再排序，所以区间是[1,n-1]
            int base = nums[i]; // 基准元素，即正在排序的元素
            int j = i - 1;
            while (j >= 0 && nums[j] > base) { // 找到基准元素的正确位置
                nums[j + 1] = nums[j]; // 将大于基准值的元素向后移动一位
                j--;
            }
            nums[j + 1] = base; // 将基准元素放到正确的位置
        }
    }

    /*
     * @author yancz
     * @description // 4.快速排序，需要进行递归调用，时间复杂度O(nlogn)，空间复杂度O(logn)，不稳定排序
     * @date 2025/3/2 17:41
     * @param nums
     * @param left
     * @param right
     * @return void
     */
    public static void quickSort(int[] nums, int left, int right) {
        if (left >= right) return; // 递归终止条件，当前区间只有一个元素或为空
        // 哨兵分组
        int pivotIndex = partitionGroup(nums, left, right);
        quickSort(nums, left, pivotIndex - 1); // 递归排序左半部分
        quickSort(nums, pivotIndex + 1, right); // 递归排序右半部分
    }

    /*
     * @author yancz
     * @description // 快速排序的哨兵分组
     * @date 2025/3/2 17:25
     * @param nums 待排序数组
     * @param left 左哨兵
     * @param right 右哨兵
     * @return int 基准元素的索引
     */
    private static int partitionGroup(int[] nums, int left, int right) {
        int pivot = nums[left]; // 选取第一个元素作为基准元素
        int i = left, j = right; // 初始化左右哨兵
        while (i < j) {
            while (i < j && nums[j] >= pivot) { // 从右往左找到第一个小于基准元素的元素
                j--;
            }
            while (i < j && nums[i] <= pivot) { // 从左往右找到第一个大于基准元素的元素
                i++;
            }
            swapElements(nums, i, j);
        }
        // 不满足i<j时，说明左右两个哨兵已经相遇，指向了同一个元素，i=j，此时将基准元素放到中间
        swapElements(nums, i, left);
        return i;
    }

    /*
     * @author yancz
     * @description // *（重点理解） 5.归并排序，时间复杂度O(nlogn)，空间复杂度O(n)，稳定排序
     * @date 2025/3/2 21:19
     * @param nums
     * @param left
     * @param right
     * @return void
     */
    public static void mergeSort(int[] nums, int left, int right) {
        if (left >= right) return; // 递归终止条件，当前区间只有一个元素或为空
        int mid = left + (right - left) / 2; // 取中间位置
        mergeSort(nums, left, mid); // 递归排序左半部分
        mergeSort(nums, mid + 1, right); // 递归排序右半部分
        merge(nums, left, mid, right);
    }

    /*
     * @author yancz
     * @description // 合并左子数组和右子数组,左子数组区间为[left,mid]，右子数组区间为[mid+1,right]
     * @date 2025/3/2 18:58
     * @param nums 待合并数组
     * @param left 子数组的起始位置
     * @param mid 子数组的中间位置
     * @param right 子数组的结束位置
     * @return void
     */
    private static void merge(int[] nums, int left, int mid, int right) {
        // 创建临时数组，用于存放合并后的结果
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) { // 当左右子数组都有元素时，进行比较并将较小的元素复制到临时数组中
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        while (i <= mid) { // 处理左子数组剩余元素
            temp[k++] = nums[i++];
        }
        while (j <= right) { // 处理右子数组剩余元素
            temp[k++] = nums[j++];
        }
        for (k = 0; k < temp.length; k++) { // 将临时数组中的元素复制到原数组中的对应区间中
            nums[left + k] = temp[k];
        }
        String s = "123";
    }

    /*
     * @author yancz
     * @description // 6.堆排序，时间复杂度O(nlogn)，空间复杂度O(1)，不稳定排序
     * @date 2025/3/3 18:26
     * @param nums
     * @return void
     */
    public static void heapSort(int[] nums) {
        // 建堆操作，堆化除了叶节点以外的其他节点
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            siftDown(nums, nums.length, i);
        }
        // 从堆中提取最大元素，循环n - 1轮
        for (int i = nums.length - 1; i > 0; i--) {
            swapElements(nums, 0, i);
            siftDown(nums, i, 0);
        }
    }

    /*
     * @author yancz
     * @description // 堆的长度为n，从节点i开始，从顶至底堆化
     * @date 2025/3/3 17:53
     * @param nums
     * @param n
     * @param i
     * @return void
     */
    private static void siftDown(int[] nums, int n, int i) {
        while (true) {
            int left = 2 * i + 1; // 左子节点
            int right = 2 * i + 2; // 右子节点
            int maxIndex = i; // 最大子节点索引
            if (left < n && nums[left] > nums[maxIndex]) { // 存在左子节点，且左子节点大于最大子节点
                maxIndex = left;
            }
            if (right < n && nums[right] > nums[maxIndex]) { // 存在右子节点，且右子节点大于最大子节点
                maxIndex = right;
            }
            if (maxIndex == i) {
                break; // 最大子节点不变，结束
            }
            // 交换最大子节点和当前节点
            swapElements(nums, i, maxIndex);
            i = maxIndex; // 继续向下堆化
        }
    }

    /*
     * @author yancz
     * @description // 7. 桶排序，时间复杂度O(n+k)，空间复杂度O(n+k)，不稳定排序
     * @date 2025/3/3 21:20
     * @param nums 待排序数据
     * @param bucketSize 桶的容量，比如10，则每个桶最多存放10个元素
     * @return void
     */
    public static void bucketSort(int[] nums, int bucketSize) {
        if (nums.length == 0) return;
        // 找出数组中的最大值最小值
        int max = getMaxMin(nums)[0];
        int min = getMaxMin(nums)[1];
        // 初始化max+1个桶，每个桶存放特定的整数值
        List<List<Integer>> buckets = initBuckets(max, min, bucketSize);
        // 将数组元素分配到各个桶中
        for (int num : nums) {
            int bucketIndex = (num - min) / bucketSize;
            buckets.get(bucketIndex).add(num);
        }
        int bucketCount = (max - min) / bucketSize + 1; // 桶的数量
        // 遍历桶合并结果
        int index = 0;
        for (int i = 0; i < bucketCount; i++) {
            List<Integer> bucket = buckets.get(i);
            Collections.sort(bucket);
            for (Integer bucketNum : bucket) {
                nums[index++] = bucketNum;
            }
        }
    }

    /*
     * @author yancz
     * @description // 初始化桶
     * @date 2025/3/3 21:14
     * @param max
     * @param min
     * @param bucketSize
     * @return List<List<Integer>>
     */
    private static List<List<Integer>> initBuckets(int max, int min, int bucketSize) {
        int bucketCount = (max - min) / bucketSize + 1;
        List<List<Integer>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        return buckets;
    }

    /*
     * @author yancz
     * @description // 获取数组中的最大值和最小值
     * @date 2025/3/3 21:11
     * @param nums
     * @return int
     */
    private static int[] getMaxMin(int[] nums) {
        int max = nums[0];
        int min = nums[0];
        for (int i : nums) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }
        return new int[]{max, min};
    }

    /*
     * @author yancz
     * @description // 8.计数排序的简单实现，只适用于整数排序，无法处理对象排序，时间复杂度O(n+k)，空间复杂度O(k)，稳定排序
     * @date 2025/3/4 12:16
     * @param nums
     * @return void
     */
    public static void countingSortNative(int[] nums) {
        int max = getMaxMin(nums)[0]; // 找出数组中的最大值
        // 统计各数字出现的次数
        int[] counter = new int[max + 1];
        for (int i : nums) {
            counter[i]++;
        }
        // 遍历counter数组，将每个数字复制到输出数组中
        int index = 0;
        for (int i = 0; i < max + 1; i++) {
            for (int j = 0; j < counter[i]; j++, index++) {
                nums[index] = i;
            }
        }
    }

    /*
     * @author yancz
     * @description // 计数排序，使用前缀和优化，时间复杂度O(n+k)，空间复杂度O(k)，稳定排序
     * @date 2025/3/4 19:09
     * @param nums
     * @return void
     */
    public static void countingSortPrefixSum(int[] nums) {
        // 获取最大值
        int max = getMaxMin(nums)[0];
        // 统计各数字出现的次数
        int[] counter = new int[max + 1];
        for (int i : nums) {
            counter[i]++;
        }
        // 求counter数组的前缀和，将出现次数转换为尾索引
        for (int i = 0; i < max; i++) {
            counter[i + 1] += counter[i];
        }
        // 倒序遍历原数组，将各个元素填入结果数组res中
        int size = nums.length;
        int[] res = new int[size];
        for (int i = size - 1; i >= 0; i--) {
            int num = nums[i];
            int prefixSum = counter[num] - 1; // 前缀和
            res[prefixSum] = num; // num放到对应的索引处
            counter[num]--; // 前缀和自减，得到下次放置num的索引
        }
        // 结果数组覆盖原数组
        System.arraycopy(res, 0, nums, 0, size);
    }

    /*
     * @author yancz
     * @description // 基数排序
     * @date 2025/3/4 19:36
     * @param nums
     * @return void
     */
    private static void radixSort(int[] nums) {
        // 获取最小值
        int min = getMaxMin(nums)[1];
        // 按照从低位到高位的顺序进行遍历
        for (int exp = 1; exp <= min; exp *= 10) {
            countingSortPrefixSum(nums);
        }
    }

    // 计数排序，根据nums的第k位进行排序，exp = 10^(k-1) */
    private static void countingSortDictionary(int[] nums, int exp) {
        // 十进制数的范围是 0~9，所以需要 10 个桶
        int[] counter = new int[10];
        int size = nums.length;
        // 统计0-9各数字出现的次数
        for (int i = 0; i < size; i++) {
            int d = digit(nums[i], exp); // 获取元素nums[i]的第k位，记为d
            counter[d]++; // 统计数字d出现的次数
        }
        // 求前缀和
        for (int i = 1; i < 10; i++) {
            counter[i] += counter[i - 1];
        }
        // 倒序遍历原数组，将各个元素填入结果数组res中
        int[] res = new int[size];
        for (int i = size - 1; i >= 0; i--) {
            int d = digit(nums[i], exp);
            int prefixSum = counter[d] - 1;
            res[prefixSum] = nums[i];
            counter[d]--;
        }
        System.arraycopy(res, 0, nums, 0, size);
    }

    // 获取元素 num 的第 k 位，其中 exp = 10^(k-1) */
    private static int digit(int num, int exp) {
        return (num / exp) % 10;
    }

    /*
     * @author yancz
     * @description // 公共方法，交换两个元素的位置
     * @date 2025/3/1 18:38
     * @param i
     * @param j
     * @return void
     */
    private static void swapElements(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /*
     * @author yancz
     * @description // 公共方法，遍历数组元素
     * @date 2025/3/1 18:41
     * @param nums
     * @return void
     */
    private static void commonPrint(int[] nums) {
        for (int i : nums) {
            System.out.print(i + "\t");
        }
        System.out.println();
        System.out.println("-------------------------------");
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2, 5, 3, 1, 4, 8, 7, 6};
        selectionSort(nums);
        System.out.println("选择排序结果：");
        commonPrint(nums);
        int[] nums2 = new int[]{2, 5, 3, 1, 4, 8, 7, 6};
//        bubbleSort(nums2);
        bubbleSortSwitchFlag(nums2);
        System.out.println("冒泡排序结果：");
        commonPrint(nums2);
        int[] nums3 = new int[]{2, 5, 3, 1, 4, 8, 7, 6};
        insertionSort(nums3);
        System.out.println("插入排序结果：");
        commonPrint(nums3);
        int[] nums4 = new int[]{2, 5, 3, 1, 4, 8, 7, 6};
        quickSort(nums4, 0, nums4.length - 1);
        System.out.println("快速排序结果：");
        commonPrint(nums4);
        int[] nums5 = new int[]{2, 5, 3, 1, 4, 8, 7, 6};
        mergeSort(nums5, 0, nums5.length - 1);
        System.out.println("归并排序结果：");
        commonPrint(nums5);
        int[] nums6 = new int[]{2, 5, 3, 1, 4, 8, 7, 6};
        heapSort(nums6);
        System.out.println("堆排序结果：");
        commonPrint(nums6);
        int[] nums7 = new int[]{2, 5, 3, 1, 4, 8, 7, 6};
        bucketSort(nums7, 5);
        System.out.println("桶排序结果：");
        commonPrint(nums7);
        int[] nums8 = new int[]{2, 5, 3, 1, 4, 8, 7, 6, 2, 6, 5, 2};
//        countingSortNative(nums8);
        countingSortPrefixSum(nums8);
        System.out.println("计数排序结果：");
        commonPrint(nums8);
        int[] nums9 = new int[]{2, 5, 3, 1, 4, 8, 7, 6, 2, 6, 5, 2};
        radixSort(nums9);
        System.out.println("基数排序结果：");
        commonPrint(nums9);
    }

}
